package com.kevinkk.graph;

import java.util.*;

/**
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 */

/**
 * 需要统计所有课程的入度，只有入度为0，才能选择这门课
 * 首先设计一个数组 indegrees 用来记录所有节点的入度
 * 用一个临接表 adj 来记录当前节点都指向了哪些节点（这样在删除这个节点后，好统计哪些节点入度会减少）
 * 再用一个队列来记录当前入度为 0 的节点
 */

public class CourseSchedule {
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] indegrees = new int[numCourses];
            List<List<Integer>> adj = new ArrayList<>();
            Deque<Integer> que = new ArrayDeque<>();
            for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());    // 首先需要用这种方式来初始化一个二维临接表
            for (int[] pre : prerequisites) {
                // 0 <- 1
                indegrees[pre[0]]++;            // 第一个节点的入度增加
                adj.get(pre[1]).add(pre[0]);    // 第二个节点可以指向第一个节点
            }
            for (int i = 0; i < numCourses; i++)    // 遍历寻找入度为 0 的节点加入队列
                if (indegrees[i] == 0) que.addLast(i);

            while (!que.isEmpty()) {
                int i = que.removeFirst();      // 删除该节点
                numCourses--;
                for (int k : adj.get(i)) {      // 那么这个节点通向的所有节点入度都要减少
                    if (--indegrees[k] == 0)    // 如果减少之后，该节点入度为 0 则加入队列
                        que.addLast(k);
                }
            }
            return numCourses == 0;
        }
    }
}
